|
In computer science, the Boyer–Moore–Horspool algorithm or Horspool's algorithm is an algorithm for finding substrings in strings. It was published by Nigel Horspool in 1980. It is a simplification of the Boyer–Moore string search algorithm which is related to the Knuth–Morris–Pratt algorithm. The algorithm trades space for time in order to obtain an average-case complexity of O(N) on random text, although it has O(MN) in the worst case, where the length of the pattern is M and the length of the search string is N. ==Description== Like Boyer–Moore, Boyer–Moore–Horspool preprocesses the pattern to produce a table containing, for each symbol in the alphabet, the number of characters that can safely be skipped. The preprocessing phase, in pseudocode, is as follows (for an alphabet of 256 symbols, i.e., bytes): function preprocess(pattern) T ← new table of 256 integers for i from 0 to 256 exclusive T() ← length(pattern) for i from 0 to length(pattern) - 1 exclusive T = needle() if i = 0 return skip i ← i - 1 skip ← skip + T[haystack[skip + length(needle) - 1]] return ''not-found'' 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Boyer–Moore–Horspool algorithm」の詳細全文を読む スポンサード リンク
|